package LeetcodeTest_thirty_five;

//1552. 两球之间的磁力
import java.util.Arrays;

public class maxDistance
{
    public static void main(String[] args)
    {
        int[] position={1,2,3,4,5,10};
        int m=3;
        System.out.println(Solutions.maxDistance(position,m));
    }
}
class Solutions {
    public static int maxDistance(int[] position, int m)
    {
        Arrays.sort(position);
        int i,low,high,middle,n,answer;;
        n=position.length;
        answer=0;
        int minLength=position[n-1]-position[0];
        for(i=0;i<n-1;i++)
        {
            if(minLength>position[i+1]-position[i])
                minLength=position[i+1]-position[i];
        }
        low=minLength;
        high=(position[n-1]-position[0])/(m-1);
        while (low<=high)
        {
            middle=(low+high)/2;
            if(checkBall(position,m,middle))
            {
                answer=middle;
                low=middle+1;
            }
            else
                high=middle-1;
        }
        return answer;
    }
    public static boolean checkBall(int[] position, int m,int maxLength) {
        int count,start;
        count=0;
        start=position[0];
        for (int i = 1; i < position.length;i++) {
            if (position[i] - start >= maxLength) {
                start = position[i];
                count++;
            }
        }
        if(count>=m)
            return true;
        else
            return false;
    }
}